package com.monotoneStack;

import java.util.Stack;

/**
 * 接雨水
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 */
public class TrappingRainWater0122_42 {
    //    public int trap(int[] height) {
//        if (height.length <= 2) return 0;
//        //单调栈思路
//        Stack<Integer> stack = new Stack<>();
//        int res = 0;
//
//        stack.push(0);
//        for (int i = 1; i < height.length; i++) {
//            int stackTop = stack.peek();
//            if (height[i] < height[stack.peek()]) {
//                stack.push(i);
//            } else if (height[i] == height[stack.peek()]) {
//                stack.pop();
//                stack.push(i);
//            } else {
//                while (!stack.isEmpty() && height[i] > height[stackTop]) {
//                    // i 下标为右侧第一个大于mid的值。 mid 为低谷
//                    int mid = stack.pop();
//                    //找 mid 左侧第一个大于的值，其实就是 stack 栈的下一个值
//                    if (!stack.isEmpty()) {
//                        int left = stack.peek();
//
//                        int h = Math.min(height[left], height[i]) - height[mid];
//                        int w = i - left - 1;
//                        int hold = h * w;
//                        res += hold;
//                        stackTop = stack.peek();
//                    }
//                }
//                stack.push(i);
//            }
//        }
//        return res;
//    }
//    public int trap(int[] height) {
//        // 暴力超时: 求每一个竖列的值，再相加
//        int sum = 0;
//        for (int i = 0; i < height.length; i++) {
//            //第一个柱子和最后一个柱子不接雨水
//            if (i == 0 || i == height.length - 1) continue;
//
//            int rHeight = height[i]; //记录右边柱子最高
//            int lHeight = height[i]; //记录左边柱子最高
//            for (int j = i + 1; j < height.length; j++) {
//                if (height[j] > rHeight) rHeight = height[j];
//            }
//            for (int j = i - 1; j >= 0; j--) {
//                if (height[j] > lHeight) lHeight = height[j];
//            }
//            int h = Math.min(lHeight, rHeight) - height[i];
//            if (h > 0) sum += h;
//        }
//        return sum;
//    }
    public int trap(int[] height) {
        // 双指针 思路
        int len = height.length;
        if(len <= 2) return 0;
        int[] maxLeft = new int[len];
        int[] maxRight = new int[len];

        //记录每个柱子左边柱子最大值
        maxLeft[0] = height[0];
        for (int i = 1; i < len; i++) {
            maxLeft[i] = Math.max(height[i],maxLeft[i-1]);
        }
        //记录每个柱子右边柱子最大值
        maxRight[len -1] = height[len -1];
        for (int i = len -2; i >=0; i--) {
            maxRight[i] = Math.max(height[i],maxRight[i+1]);
        }

        //求和
        int sum=0;
        for (int i = 0; i < len; i++) {
            int count = Math.min(maxLeft[i], maxRight[i]) - height[i];
            if(count>0) sum += count;
        }
        return sum;
    }
}

